A cache is an auxiliary set of data entries. A cache entry includes a static copy of a data object corresponding to a source data object. Typically, a cache is used to temporarily store data closer to a data consumer than a data source, or to temporarily hold data that is generated as needed. Multiple caches may be used cooperatively and/or in a hierarchical manner. Example uses for a cache include, but are not limited to, using a cache to accelerate access by a computer processor to data held in a comparatively slower storage medium, e.g., a hard drive; using a cache to shield a database query engine from redundant queries; and using a cache to manage distribution of data in a content delivery network, e.g., a distributed Web cache in the Internet. It is typically less computationally expensive, or resource demanding, to use a cache than to directly fetch a requested data object from an original source.
When an object is first loaded into a cache, the object data is an identical copy of its corresponding source data. However, the cached data object may become invalid. For example, a cache entry may become invalid when the source data is modified, deleted, or replaced. A cache entry may be invalid if the entry has expired, if access is restricted, or if the entry is otherwise disqualified. Some cache implementations purge data entries that are identified as invalid.
In some typical cache implementations, the cache uses a replacement policy to select particular cache entries to remove from the cache. For example, if a new cache entry requires more space than is presently available, some cache implementations will use a replacement policy to select entries, and remove the selected entries to create space for the new entry. Examples of replacement policies include the most recently used “MRU” policy, the least recently used “LRU” policy, and the segmented least recently used “SLRU” policy. In each of these replacement policies, the cache implementation keeps track of access or usage statistics for cache entries. When the cache is full, the cache entry, or entries, identified by the policy can be cleared from the cache to make space for a new cache entry. In MRU, the most recently used entry is removed; in LRU, the least recently used entry is removed; and in SLRU, the least recently used entry in a “probationary” segment is removed. Cache entries are promoted out of the probationary segment after satisfying a utility criteria, e.g., multiple requests for the same cache entry. Stale cache entries may be demoted back to the probationary segment. If a removed cache entry is later requested, after having been cleared from the cache, a new cache entry can be created by re-fetching the source data from either another cooperative cache or from a data source. Other replacement policies, or eviction policies, may also be used.